<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    820. Find Eventual Safe States
   </h1>
   <p>
    In a directed graph, we start at some node and every turn, walk along a directed edge of the graph.&nbsp; If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.
   </p>
   <p>
    Now, say our starting node is
    <em>
     eventually safe&nbsp;
    </em>
    if and only if we must eventually walk to a terminal node.&nbsp; More specifically, there exists a natural number
    <code>
     K
    </code>
    so that for any choice of where to walk, we must have stopped at a terminal node in less than
    <code>
     K
    </code>
    steps.
   </p>
   <p>
    Which nodes are eventually safe?&nbsp; Return them as an array in sorted order.
   </p>
   <p>
    The directed graph has
    <code>
     N
    </code>
    nodes with labels
    <code>
     0, 1, ..., N-1
    </code>
    , where
    <code>
     N
    </code>
    is the length of
    <code>
     graph
    </code>
    .&nbsp; The&nbsp;graph is given in the following form:
    <code>
     graph[i]
    </code>
    is a list of labels
    <code>
     j
    </code>
    such that
    <code>
     (i, j)
    </code>
    is a directed edge of the graph.
   </p>
   <pre>
<strong>Example:</strong>
<strong>Input:</strong> graph = [[1,2],[2,3],[5],[0],[5],[],[]]
<strong>Output:</strong> [2,4,5,6]
Here is a diagram of the above graph.

</pre>
   <p>
    <img alt="Illustration of graph" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/17/picture1.png" style="height:86px; width:300px">
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ul>
    <li>
     <code>
      graph
     </code>
     will have length at most
     <code>
      10000
     </code>
     .
    </li>
    <li>
     The number of edges in the graph will not exceed
     <code>
      32000
     </code>
     .
    </li>
    <li>
     Each
     <code>
      graph[i]
     </code>
     will be a sorted list of different integers, chosen within the range
     <code>
      [0, graph.length - 1]
     </code>
     .
    </li>
   </ul>
  </div>
  <div>
   <h1 class="question_title">
    820. 找到最终的安全状态
   </h1>
   <p>
    在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。
   </p>
   <p>
    现在, 如果我们最后能走到终点，那么我们的起始节点是
    <em>
     最终安全
    </em>
    的。 更具体地说, 存在一个自然数
    <code>
     K
    </code>
    ,&nbsp; 无论选择从哪里开始行走, 我们走了不到
    <code>
     K
    </code>
    步后必能停止在一个终点。
   </p>
   <p>
    哪些节点最终是安全的？ 结果返回一个有序的数组。
   </p>
   <p>
    该有向图有
    <code>
     N
    </code>
    个节点，标签为
    <code>
     0, 1, ..., N-1
    </code>
    , 其中
    <code>
     N
    </code>
    是&nbsp;
    <code>
     graph
    </code>
    &nbsp;的节点数.&nbsp; 图以以下的形式给出:
    <code>
     graph[i]
    </code>
    是节点
    <code>
     j
    </code>
    的一个列表，满足
    <code>
     (i, j)
    </code>
    是图的一条有向边。
   </p>
   <pre>
<strong>示例：</strong>
<strong>输入：</strong>graph = [[1,2],[2,3],[5],[0],[5],[],[]]
<strong>输出：</strong>[2,4,5,6]
这里是上图的示意图。

</pre>
   <p>
    <img alt="Illustration of graph" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/17/picture1.png" style="height:86px; width:300px">
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ul>
    <li>
     <code>
      graph
     </code>
     节点数不超过
     <code>
      10000
     </code>
     .
    </li>
    <li>
     图的边数不会超过
     <code>
      32000
     </code>
     .
    </li>
    <li>
     每个
     <code>
      graph[i]
     </code>
     被排序为不同的整数列表， 在区间
     <code>
      [0, graph.length - 1]
     </code>
     &nbsp;中选取。
    </li>
   </ul>
  </div>
 </body>
</html>